#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <queue>

using namespace std;

// 哈夫曼树节点结构
struct HTNode
{
    int weight;
    int parent;
    int lchild;
    int rchild;
    char ch;
};

// 哈夫曼编码结构
struct HCode
{
    char ch;
    string code;
};

// 用于选择两个最小权重的节点
void select(const vector<HTNode> &ht, int k, int &s1, int &s2)
{
    s1 = -1;
    // 找到第一个权值最小的节点
    for (int i = 1; i <= k; ++i)
    {
        if (ht[i].parent == 0)
        {
            if (s1 == -1 || ht[i].weight < ht[s1].weight)
            {
                s1 = i;
            }
        }
    }

    s2 = -1;
    // 找到第二个权值最小的节点
    for (int i = 1; i <= k; ++i)
    {
        if (ht[i].parent == 0 && i != s1)
        {
            if (s2 == -1 || ht[i].weight < ht[s2].weight)
            {
                s2 = i;
            }
        }
    }
}

void process(const string &input_str)
{
    // 过滤输入，只保留小写字母
    string filtered_str = "";
    for (char c : input_str)
    {
        if (c >= 'a' && c <= 'z')
        {
            filtered_str += c;
        }
    }

    // 1. 统计字符频率
    map<char, int> freqs;
    for (char c : filtered_str)
    {
        freqs[c]++;
    }

    vector<pair<char, int>> sorted_freqs(freqs.begin(), freqs.end());
    sort(sorted_freqs.begin(), sorted_freqs.end());

    // 输出第一行：频率
    for (size_t i = 0; i < sorted_freqs.size(); ++i)
    {
        cout << sorted_freqs[i].first << ":" << sorted_freqs[i].second << (i == sorted_freqs.size() - 1 ? "" : " ");
    }
    cout << endl;

    int n = sorted_freqs.size();
    if (n == 0)
    {
        cout << endl
             << endl; // 空串编码和解码结果为空
        return;
    }

    int m;
    if (n == 1)
    { // 特殊处理只有一个字符的情况
        m = 1;
    }
    else
    {
        m = 2 * n - 1;
    }

    vector<HTNode> ht(m + 1);
    map<char, int> char_to_index;

    for (int i = 1; i <= n; ++i)
    {
        ht[i] = {sorted_freqs[i - 1].second, 0, 0, 0, sorted_freqs[i - 1].first};
        char_to_index[sorted_freqs[i - 1].first] = i;
    }

    // 2. 构建哈夫曼树
    if (n > 1)
    {
        for (int i = n + 1; i <= m; ++i)
        {
            int s1 = 0, s2 = 0;
            select(ht, i - 1, s1, s2);
            ht[s1].parent = i;
            ht[s2].parent = i;
            ht[i] = {ht[s1].weight + ht[s2].weight, 0, s1, s2, '\0'};
        }
    }

    // 输出第二部分：哈夫曼树存储结构
    for (int i = 1; i <= m; ++i)
    {
        cout << i << " " << ht[i].weight << " " << ht[i].parent << " " << ht[i].lchild << " " << ht[i].rchild << endl;
    }

    // 3. 生成哈夫曼编码
    vector<HCode> huffman_codes;
    map<char, string> code_map;
    if (n > 1)
    {
        for (int i = 1; i <= n; ++i)
        {
            string code = "";
            int current = i;
            int p = ht[current].parent;
            while (p != 0)
            {
                if (ht[p].lchild == current)
                {
                    code = "0" + code;
                }
                else
                {
                    code = "1" + code;
                }
                current = p;
                p = ht[current].parent;
            }
            huffman_codes.push_back({ht[i].ch, code});
            code_map[ht[i].ch] = code;
        }
    }
    else
    { // 只有一个字符的特殊情况
        huffman_codes.push_back({ht[1].ch, "0"});
        code_map[ht[1].ch] = "0";
    }

    sort(huffman_codes.begin(), huffman_codes.end(), [](const HCode &a, const HCode &b)
         { return a.ch < b.ch; });

    // 输出第三部分：哈夫曼编码
    for (size_t i = 0; i < huffman_codes.size(); ++i)
    {
        cout << huffman_codes[i].ch << ":" << huffman_codes[i].code << (i == huffman_codes.size() - 1 ? "" : " ");
    }
    cout << endl;

    // 4. 编码
    string encoded_str = "";
    for (char c : filtered_str)
    {
        encoded_str += code_map[c];
    }
    cout << encoded_str << endl;

    // 5. 解码
    string decoded_str = "";
    if (!encoded_str.empty())
    {
        if (n > 1)
        {
            int current_node = m; // 从根节点开始
            for (char bit : encoded_str)
            {
                if (bit == '0')
                {
                    current_node = ht[current_node].lchild;
                }
                else
                {
                    current_node = ht[current_node].rchild;
                }

                if (ht[current_node].lchild == 0 && ht[current_node].rchild == 0)
                { // 是叶子节点
                    decoded_str += ht[current_node].ch;
                    current_node = m; // 回到根节点
                }
            }
        }
        else
        { // 只有一个字符的情况
            for (size_t i = 0; i < encoded_str.length(); ++i)
            {
                decoded_str += ht[1].ch;
            }
        }
    }
    cout << decoded_str << endl;
}

int main()
{
    string line;
    while (getline(cin, line) && line != "0")
    {
        process(line);
    }
    return 0;
}